
//堆排序1.0 升序<-->用<-->小堆 降序<-->用<-->大堆
//问题：
//1、需要有一个堆数据结构存在 才能创建堆对象
//2、在堆对象空间再创建一个数组 调整后回写 空间复杂度为 O(N)
void Low_HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < n; ++i)
	{
		HeapPush(&hp, a[i]);
	}

	int i = 0;
	while (!HeapEmpty(&hp))
	{
		a[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
//堆排序2.0 升序<-->建<-->大堆 降序<-->建<-->大堆
void Plus_HeapSort(int* a, int n)
{
//一、建堆
// 	1.0 上调建堆法 O(N*logN)
// 	将数组a传参后 假设原数组就是一颗树 只不过这棵树待调整
// 	上调法：遍历数组 从1到n-1 上调至合适位置
//  定位父节点下标 int parent = (child - 1) / 2 -->  i从1开始而非0
	
    /*
	for (int i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}
    */
//  2.0 下调建堆法 O(N)
// 	将数组a传参后 假设原数组就是一颗树 只不过这棵树待调整
// 	下调法：遍历数组 叶子节点无孩子不用下调 
//          从倒数第一个非叶子节点开始遍历至根节点
// 	        倒数第一个非叶子节点：末节点的父亲
// 	        公式计算父节点下标 int parent = (child - 1) / 2
// 	        末节点下标：n - 1 - 1
//  设左孩子较小 int child = parent * 2 + 1;
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}
//二、排序(升序法：将大值一次排到尾部 建大堆-->根最大) O(N*logN)
	//定位末节点
	int end = n - 1;
	//排序 遍历已经调好位置的大堆
	while (end > 0)
	{
		//头尾交换(最大的值(根结点)与末节点的值交换)
		//下调
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		//下标前移
		--end;
	}
}

//测试堆排序
void TestHeapSort()
{
	int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	Plus_HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	TestHeapSort();

	return 0;
}
